#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
#include <iostream>
using std::cin;
using std::cout;
template <class T>
class List
{
    struct Node
    {
        T data;
        Node *prev, *next;
        Node(const T &d = T(), Node *p = NULL, Node *n = NULL) : data(d), prev(p), next(n) {}
    };
    int size;
    Node *head;
    Node *tail;
    void init()
    {
        size = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }

public:
    friend class const_iterator;
    friend class iterator;
    class const_iterator
    {
    protected:
        Node *current;
        T &retrieve() const
        {
            return current->data;
        }
        const_iterator(Node *p) : current(p) {}
        friend class List<T>;

    public:
        const_iterator() : current(NULL) {}
        const T &operator*() const
        {
            return retrieve();
        }
        const_iterator &operator++()
        {
            current = current->next;
            return *this;
        }
        const_iterator operator++(int)
        {
            const_iterator old = *this;
            ++(*this);
            return old;
        }
        const_iterator &operator--()
        {
            current = current->prev;
            return *this;
        }
        const_iterator operator--(int)
        {
            const_iterator old = *this;
            --(*this);
            return old;
        }
        bool operator==(const const_iterator &rhs) const
        {
            return current == rhs.current;
        }
        bool operator!=(const const_iterator &rhs) const
        {
            return current != rhs.current;
        }
    };
    class iterator : public const_iterator
    {
    protected:
        iterator(Node *p) : const_iterator(p) {}
        friend class List<T>;

    public:
        iterator() {}
        T &operator*()
        {
            return const_iterator::retrieve();
        }
        const T &operator*() const
        {
            return const_iterator::operator*();
        }
        iterator &operator++()
        {
            const_iterator::current = const_iterator::current->next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator old = *this;
            ++(*this);
            return old;
        }
        iterator &operator--()
        {
            const_iterator::current = const_iterator::current->prev;
            return *this;
        }
        iterator operator--(int)
        {
            iterator old = *this;
            --(*this);
            return old;
        }
    };
    List()
    {
        init();
    }
    List(const List<T> &l)
    {
        init();
        operator=(l);
    }
    ~List()
    {
        Clear();
        delete head;
        delete tail;
    }
    const List &operator=(const List &l);
    int Size() const
    {
        return size;
    }
    bool Empty() const
    {
        return size == 0;
    }
    void Clear()
    {
        while (!Empty())
            Pop_front();
    }

    iterator begin()
    {
        return iterator(head->next);
    }
    const_iterator begin() const
    {
        return const_iterator(head->next);
    }
    iterator end()
    {
        return iterator(tail);
    }
    const_iterator end() const
    {
        return const_iterator(tail);
    }

    T &Front()
    {
        return *begin();
    }
    const T &Front() const
    {
        return *begin();
    }
    T &Back()
    {
        return *--end();
    }
    const T &Back() const
    {
        return *--end();
    }
    void Push_front(const T &item)
    {
        Insert(begin(), item);
    }
    void Push_back(const T &item)
    {
        Insert(end(), item);
    }
    void Pop_front()
    {
        Erase(begin());
    }
    void Pop_back()
    {
        Erase(--end());
    }
    iterator Erase(iterator itr);
    iterator Insert(iterator itr, const T &item);
    T &RemoveMin()
    {
        T res = *(this->begin());
        iterator i = this->begin();
        iterator j = i;
        for (; i != this->end(); i++)
            if (*(i) < res)
            {
                res = *(i);
                j = i;
            }
        this->Erase(j);
        return res;
    }
    void print()
    {
        for (iterator i = begin(); i != end(); i++)
            std::cout << *(i) << " ";
        std::cout << std::endl;
    }
};
template <class T>
const List<T> &List<T>::operator=(const List<T> &l)
{
    Clear();
    for (const_iterator itr = l.begin(); itr != l.end(); ++itr)
        Push_back(*itr);
    return *this;
}

template <class T>
typename List<T>::iterator List<T>::Erase(iterator itr)
{
    Node *p = itr.current;
    iterator re(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    size--;
    return re;
}
template <class T>
typename List<T>::iterator List<T>::Insert(iterator itr, const T &item)
{
    Node *p = itr.current;
    size++;
    p->prev->next = new Node(item, p->prev, p);
    p->prev = p->prev->next;
    return iterator(p->prev);
}

#endif
